/*-------------------------------------------------------------------------
 *
 * analyzejoins.c
 *	  用于在初始查询分析后简化连接的例程
 *
 * 尽管我们在prep/prepjointree.c中执行了大量连接简化，
 * 但是某些优化无法在该阶段执行，因缺乏关于查询的详细信息。
 * 本里程中的例程在initsplan.c完成工作后被调用，
 * 并可以根据提取的信息进行额外的连接移除和简化步骤。
 * 代价是，在修改查询时我们必须更加努力清理，
 * 因为派生数据结构也必须更新。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/optimizer/plan/analyzejoins.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/joininfo.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
#include "utils/lsyscache.h"

/* 本地函数 */
static bool fc_join_is_removable(PlannerInfo *fc_root, SpecialJoinInfo *fc_sjinfo);
static void fc_remove_rel_from_query(PlannerInfo *fc_root, int fc_relid,
								  Relids fc_joinrelids);
static List *fc_remove_rel_from_joinlist(List *fc_joinlist, int fc_relid, int *fc_nremoved);
static bool fc_rel_supports_distinctness(PlannerInfo *fc_root, RelOptInfo *fc_rel);
static bool fc_rel_is_distinct_for(PlannerInfo *fc_root, RelOptInfo *fc_rel,
								List *fc_clause_list);
static Oid	fc_distinct_col_search(int fc_colno, List *fc_colnos, List *fc_opids);
static bool fc_is_innerrel_unique_for(PlannerInfo *fc_root,
								   Relids fc_joinrelids,
								   Relids fc_outerrelids,
								   RelOptInfo *fc_innerrel,
								   JoinType fc_jointype,
								   List *fc_restrictlist);



/*
 * remove_useless_joins
 *		检查实际上不需要加入的关系，并将其从查询中移除。
 *
 * 我们传入当前的 joinlist 并返回更新后的列表。其他
 * 必须更新的数据结构可以通过 "root" 访问。
 */
List * remove_useless_joins(PlannerInfo *fc_root, List *fc_joinlist)
{
	ListCell   *fc_lc;

	/*
	 * 我们只对左连接的关系感兴趣，因此我们可以
	 * 扫描 join_info_list 以便轻松找到它们。
	 */
restart:
	foreach(fc_lc, fc_root->join_info_list)
	{
		SpecialJoinInfo *fc_sjinfo = (SpecialJoinInfo *) lfirst(fc_lc);
		int			fc_innerrelid;
		int			fc_nremoved;

		/* 如果不可移除则跳过 */
		if (!fc_join_is_removable(fc_root, fc_sjinfo))
			continue;

		/*
 * 目前，join_is_removable 仅在 sjinfo 的 righthand 是单个 baserel 时成功。
 * 将该关系从查询和 joinlist 中移除。
 */
		fc_innerrelid = bms_singleton_member(fc_sjinfo->min_righthand);

		fc_remove_rel_from_query(fc_root, fc_innerrelid,
							  bms_union(fc_sjinfo->min_lefthand,
										fc_sjinfo->min_righthand));

		/* 我们验证从 joinlist 中恰好移除一个引用 */
		fc_nremoved = 0;
		fc_joinlist = fc_remove_rel_from_joinlist(fc_joinlist, fc_innerrelid, &fc_nremoved);
		if (fc_nremoved != 1)
			elog(ERROR, "failed to find relation %d in joinlist", fc_innerrelid);

		/*
 * 我们也可以从列表中删除这个 SpecialJoinInfo，因为它不再
 * 相关。（由于我们将立即重新启动 foreach 循环，因此我们不处理
 * foreach_delete_current。）
 */
		fc_root->join_info_list = list_delete_cell(fc_root->join_info_list, fc_lc);

		/*
 * 重新启动扫描。这是必要的，以确保独立于 join_info_list 的
 * 顺序找到所有可移除的连接（注意，移除 attr_needed 位可能使
 * 一个连接看起来可移除，而之前却不是）。
 */
		goto restart;
	}

	return fc_joinlist;
}

/*
 * clause_sides_match_join
 *	  确定一个连接子句是否适合在此连接中使用。
 *
 * 我们已经知道该子句是一个只引用当前连接中关系的二元操作子句。
 * 这里的关键是检查它是否具有“outerrel_expr op innerrel_expr”或
 * “innerrel_expr op outerrel_expr”的形式，而不是在任一侧混合外部和内部变量。
 * 如果匹配，我们设置临时标志 outer_is_left 来识别哪个侧是哪个。
 */
static inline bool fc_clause_sides_match_join(RestrictInfo *fc_rinfo, Relids fc_outerrelids,
						Relids fc_innerrelids)
{
	if (bms_is_subset(fc_rinfo->left_relids, fc_outerrelids) &&
		bms_is_subset(fc_rinfo->right_relids, fc_innerrelids))
	{
		/* 左侧是外部 */
		fc_rinfo->outer_is_left = true;
		return true;
	}
	else if (bms_is_subset(fc_rinfo->left_relids, fc_innerrelids) &&
			 bms_is_subset(fc_rinfo->right_relids, fc_outerrelids))
	{
		/* 右侧是外部 */
		fc_rinfo->outer_is_left = false;
		return true;
	}
	return false;				/* 对这些输入关系不适用 */
}

/*
 * join_is_removable
 *	  检查我们是否根本不需要执行这个特殊连接，因为它只是
 *	  会重复它的左输入。
 *
 * 对于左连接的情况，如果连接条件无法匹配超过一个内侧行，
 * 则这一点成立。（还有其他可能有趣的情况，但我们没有
 * 基础设施来证明它们。）我们还必须检查内侧不生成
 * 连接上方所需的任何变量。
 */
static bool fc_join_is_removable(PlannerInfo *fc_root, SpecialJoinInfo *fc_sjinfo)
{
	int			fc_innerrelid;
	RelOptInfo *fc_innerrel;
	Relids		fc_joinrelids;
	List	   *fc_clause_list = NIL;
	ListCell   *fc_l;
	int			fc_attroff;

	/*
 * 必须是一个非延迟左连接到单个 baserel，否则我们将无法
 * 对其进行任何操作。
 */
	if (fc_sjinfo->jointype != JOIN_LEFT ||
		fc_sjinfo->delay_upper_joins)
		return false;

	if (!bms_get_singleton_member(fc_sjinfo->min_righthand, &fc_innerrelid))
		return false;

	/*
 * 永远不要尝试消除左连接到查询结果关系。虽然在标准 SQL
 * 中的语法是不可能的情况，但 MERGE 将构建一个看起来完全
 * 像那样的连接树。
 */
	if (fc_innerrelid == fc_root->parse->resultRelation)
		return false;

	fc_innerrel = find_base_rel(fc_root, fc_innerrelid);

	/*
 * 在检查是否需要任何 innerrel 变量以上的 join 之前，先快速
 * 检查以消除我们肯定无法证明 innerrel 唯一性的情况。
 */
	if (!fc_rel_supports_distinctness(fc_root, fc_innerrel))
		return false;

	/* 计算我们正在考虑的连接的 relid 集合 */
	fc_joinrelids = bms_union(fc_sjinfo->min_lefthand, fc_sjinfo->min_righthand);

	/*
 * 如果在连接上方使用内侧关系的任何属性，则无法移除连接。
 *
 * 注意，这个测试仅检测在更高连接条件和目标列表中使用内侧
 * 关系的属性。在该连接的下推条件中也可能存在这样的属性。
 * 我们在下面检查这种情况。
 *
 * 作为微小的优化，似乎从 max_attr 开始并倒计数比从 min_attr
 * 开始并计数更好，基于系统属性不太可能被需要，因此应该最后
 * 进行测试。
 */
	for (fc_attroff = fc_innerrel->max_attr - fc_innerrel->min_attr;
		 fc_attroff >= 0;
		 fc_attroff--)
	{
		if (!bms_is_subset(fc_innerrel->attr_needed[fc_attroff], fc_joinrelids))
			return false;
	}

	/*
 * 同样检查内侧关系未被任何将在连接上方使用的 PlaceHolderVars 需要。
 * 我们只需在这样的 PHV 实际引用某些内侧关系属性时失败；但
 * 由于进行该检查的成本相对较高，因此我们首先检查 ph_eval_at，
 * 如果 PHV 使用任何内侧关系属性作为非横向引用，则必须提到内
 * 侧关系。注意，如果 PHV 的语法作用域仅是内侧关系，即使
 * PHV 没有变量，我们也无法删除该关系。
 */
	foreach(fc_l, fc_root->placeholder_list)
	{
		PlaceHolderInfo *fc_phinfo = (PlaceHolderInfo *) lfirst(fc_l);

		if (bms_overlap(fc_phinfo->ph_lateral, fc_innerrel->relids))
			return false;		/* 它横向引用了 innerrel */
		if (bms_is_subset(fc_phinfo->ph_needed, fc_joinrelids))
			continue;			/* PHV 在连接上方未被使用 */
		if (!bms_overlap(fc_phinfo->ph_eval_at, fc_innerrel->relids))
			continue;			/* 它肯定没有引用 innerrel */
		if (bms_is_subset(fc_phinfo->ph_eval_at, fc_innerrel->relids))
			return false;		/* 没有其他地方可以评估 PHV */
		if (bms_overlap(pull_varnos(fc_root, (Node *) fc_phinfo->ph_var->phexpr),
						fc_innerrel->relids))
			return false;		/* 它确实引用了 innerrel */
	}

	/*
 * 搜索约束内侧关系与外侧关系或伪常数的可合并连接子句。
 * 如果一个运算符是可合并的，那么它在某些 btree 操作类中表现得
 * 像等价关系，因此这是我们想要的。可合并性测试还消除了包含
 * 易失性函数的子句，我们不能依赖于那个。
 */
	foreach(fc_l, fc_innerrel->joininfo)
	{
		RestrictInfo *fc_restrictinfo = (RestrictInfo *) lfirst(fc_l);

		/*
 * 如果它不是这个外连接的连接子句，我们无法使用它。
 * 注意，如果子句被下推，那么它在逻辑上是来自外连接之上，
 * 即使它没有引用其他关系（例如，它可能来自 WHERE）。
 */
		if (RINFO_IS_PUSHED_DOWN(fc_restrictinfo, fc_joinrelids))
		{
			/*
 * 如果这样的子句实际引用了内侧关系，则必须不允许
 * 移除连接。尽管之前的 attr_needed 检查了，但由于推入子句
 * 可能引用了该关系，因此我们必须检查这一点。
 */
			if (bms_is_member(fc_innerrelid, fc_restrictinfo->clause_relids))
				return false;
			continue;			/* 否则，忽略；在这里无用 */
		}

		/* 如果不是可合并连接子句，则忽略 */
		if (!fc_restrictinfo->can_join ||
			fc_restrictinfo->mergeopfamilies == NIL)
			continue;			/* 不是可合并连接的 */

		/*
 * 检查子句是否具有“外部 op 内部”或“内部 op 外部”的形式，
 * 如果是，则标记哪个侧是内部。
 */
		if (!fc_clause_sides_match_join(fc_restrictinfo, fc_sjinfo->min_lefthand,
									 fc_innerrel->relids))
			continue;			/* 对这些输入关系不适用 */

		/* 好的，添加到列表 */
		fc_clause_list = lappend(fc_clause_list, fc_restrictinfo);
	}

	/*
 * 既然我们有相关的等式连接子句，尝试证明 innerrel 是唯一的。
 */
	if (fc_rel_is_distinct_for(fc_root, fc_innerrel, fc_clause_list))
		return true;

	/*
 * 总有一天检查其他方法以建立唯一性会很好。
 */
	return false;
}



/*
 * 从规划器的数据结构中移除目标 relid，前提是
 * 确定没有必要将其包含在查询中。
 *
 * 我们这里并不是特别彻底。我们必须确保 rel
 * 不再被视为 baserel，并且其他 baserels 的属性
 * 在涉及该 rel 的连接中不再被标记为需要。 
 * 此外，涉及该 rel 的连接条件必须从 joininfo 
 * 列表中删除，但只有在它们属于由 joinrelids 
 * 标识的外连接时。
 */
static void fc_remove_rel_from_query(PlannerInfo *fc_root, int fc_relid, Relids fc_joinrelids)
{
	RelOptInfo *fc_rel = find_base_rel(fc_root, fc_relid);
	List	   *fc_joininfos;
	Index		fc_rti;
	ListCell   *fc_l;

	/*
	 * 将 rel 标记为“无效”，以表明它不再是连接树的一部分。
	 * （完全将其从 baserel 数组中移除似乎风险太大。）
	 */
	fc_rel->reloptkind = RELOPT_DEADREL;

	/*
	 * 从其他 baserels 的 attr_needed 数组中删除对该 rel 的引用。
	 */
	for (fc_rti = 1; fc_rti < fc_root->simple_rel_array_size; fc_rti++)
	{
		RelOptInfo *fc_otherrel = fc_root->simple_rel_array[fc_rti];
		int			fc_attroff;

		/* 可能会有空位对应于非基础关系的RTE */
		if (fc_otherrel == NULL)
			continue;

		Assert(fc_otherrel->relid == fc_rti); /* 对数组进行完整性检查 */

		/* 处理目标 rel 本身没有意义 */
		if (fc_otherrel == fc_rel)
			continue;

		for (fc_attroff = fc_otherrel->max_attr - fc_otherrel->min_attr;
			 fc_attroff >= 0;
			 fc_attroff--)
		{
			fc_otherrel->attr_needed[fc_attroff] =
				bms_del_member(fc_otherrel->attr_needed[fc_attroff], fc_relid);
		}
	}

	/*
	 * 同样，从 SpecialJoinInfo 数据结构中删除引用。
	 *
	 * 这在我们删除的外连接嵌套在其他外连接中的情况下是相关的：
	 * 上层连接的 relid 集必须进行调整。目标外连接的右侧
	 * 此处将被置为空，但这没关系，因为调用者将完全删除
	 * 该 SpecialJoinInfo。
	 */
	foreach(fc_l, fc_root->join_info_list)
	{
		SpecialJoinInfo *fc_sjinfo = (SpecialJoinInfo *) lfirst(fc_l);

		fc_sjinfo->min_lefthand = bms_del_member(fc_sjinfo->min_lefthand, fc_relid);
		fc_sjinfo->min_righthand = bms_del_member(fc_sjinfo->min_righthand, fc_relid);
		fc_sjinfo->syn_lefthand = bms_del_member(fc_sjinfo->syn_lefthand, fc_relid);
		fc_sjinfo->syn_righthand = bms_del_member(fc_sjinfo->syn_righthand, fc_relid);
	}

	/*
	 * 同样，从 PlaceHolderVar 数据结构中移除引用，
	 * 完全移除任何不再需要的占位符。
	 *
	 * 移除比看起来要复杂得多：我们可以移除在目标 rel 和/或
	 * 连接条件中使用的 PHV，但不能移除在连接伙伴 rel 上
	 * 或连接以上使用的 PHV。区分在伙伴 rel 上使用的 PHV
	 * 和在连接条件中使用的 PHV 并不是那么容易，因为它们
	 * 都会有 ph_needed 集合，且这些集合都是 joinrelids 的子集。
	 * 然而，在伙伴 rel 上使用的 PHV 不可能在 ph_eval_at 中
	 * 包含目标 rel，因此我们在决定是移除还是只更新 PHV 时
	 * 会进行检查。join_is_removable 中没有相应的测试，因为
	 * 它不需要区分这些情况。
	 */
	foreach(fc_l, fc_root->placeholder_list)
	{
		PlaceHolderInfo *fc_phinfo = (PlaceHolderInfo *) lfirst(fc_l);

		Assert(!bms_is_member(fc_relid, fc_phinfo->ph_lateral));
		if (bms_is_subset(fc_phinfo->ph_needed, fc_joinrelids) &&
			bms_is_member(fc_relid, fc_phinfo->ph_eval_at))
			fc_root->placeholder_list = foreach_delete_current(fc_root->placeholder_list,
															fc_l);
		else
		{
			fc_phinfo->ph_eval_at = bms_del_member(fc_phinfo->ph_eval_at, fc_relid);
			Assert(!bms_is_empty(fc_phinfo->ph_eval_at));
			fc_phinfo->ph_needed = bms_del_member(fc_phinfo->ph_needed, fc_relid);
		}
	}

	/*
	 * 从 joininfo 列表中移除任何引用 rel 的连接条件。
	 *
	 * 在某些情况下，删除对目标 rel 的引用后必须重新放回
	 * 一个连接条件。这可能发生在伪常量和外连接延迟条件中，
	 * 它们可能被标记为需要该 rel，以便强制它们在连接或
	 * 以上进行评估。不过，我们不能仅仅将它们丢弃。
	 * 只有逻辑上属于被丢弃的外连接的连接条件才能从查询中
	 * 移除。
	 *
	 * 我们必须在开始循环之前复制 rel 的旧 joininfo 列表，
	 * 因为否则 remove_join_clause_from_rels 会在我们扫描时
	 * 销毁该列表。
	 */
	fc_joininfos = list_copy(fc_rel->joininfo);
	foreach(fc_l, fc_joininfos)
	{
		RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_l);

		remove_join_clause_from_rels(fc_root, fc_rinfo, fc_rinfo->required_relids);

		if (RINFO_IS_PUSHED_DOWN(fc_rinfo, fc_joinrelids))
		{
			/* 重新检查连接条件是否实际上引用了目标 rel */
			Assert(!bms_is_member(fc_relid, fc_rinfo->clause_relids));

			/*
			 * required_relids 可能与其他任何东西不共享，
			 * 但为了安全起见，我们还是复制一份。
			 */
			fc_rinfo->required_relids = bms_copy(fc_rinfo->required_relids);
			fc_rinfo->required_relids = bms_del_member(fc_rinfo->required_relids,
													fc_relid);
			distribute_restrictinfo_to_rels(fc_root, fc_rinfo);
		}
	}

	/*
	 * root->fkey_list 中可能有对该 rel 的引用，但如果有的话，
	 * match_foreign_keys_to_quals() 会将其删除。
	 */
}

/*
 * 从 joinlist 结构中移除目标 relid 的任何出现。
 *
 * 建立一个全新的列表结构是最简单的，所以我们以这种方式处理。
 * 效率在这里不是大问题。
 *
 * *nremoved 会根据移除的出现次数递增（应该恰好为 1，
 * 但调用者会检查这一点）。
 */
static List * fc_remove_rel_from_joinlist(List *fc_joinlist, int fc_relid, int *fc_nremoved)
{
	List	   *fc_result = NIL;
	ListCell   *fc_jl;

	foreach(fc_jl, fc_joinlist)
	{
		Node	   *fc_jlnode = (Node *) lfirst(fc_jl);

		if (IsA(fc_jlnode, RangeTblRef))
		{
			int			fc_varno = ((RangeTblRef *) fc_jlnode)->rtindex;

			if (fc_varno == fc_relid)
				(*fc_nremoved)++;
			else
				fc_result = lappend(fc_result, fc_jlnode);
		}
		else if (IsA(fc_jlnode, List))
		{
			/* 递归处理子问题 */
			List	   *fc_sublist;

			fc_sublist = fc_remove_rel_from_joinlist((List *) fc_jlnode,
											   fc_relid, fc_nremoved);
			/* 避免在结果中包含空子列表 */
			if (fc_sublist)
				fc_result = lappend(fc_result, fc_sublist);
		}
		else
		{
			elog(ERROR, "unrecognized joinlist node type: %d",
				 (int) nodeTag(fc_jlnode));
		}
	}

	return fc_result;
}


/*
 * reduce_unique_semijoins
 *		检查是否有半连接可以简化为普通内连接，
 *		因为内关系在连接条件上是可证明唯一的。
 *
 * 理想情况下，这应在 reduce_outer_joins 过程中发生，
 * 但在那时我们没有足够的信息。
 *
 * 为了在适用时执行强度简化，我们只需从 root->join_info_list
 * 中删除半连接的 SpecialJoinInfo。（我们不在乎修复查询
 * 连接树中归因于它的连接类型，因为之后不会再参考它。）
 */
void reduce_unique_semijoins(PlannerInfo *fc_root)
{
	ListCell   *fc_lc;

	/*
	 * 扫描 join_info_list 以查找半连接。
	 */
	foreach(fc_lc, fc_root->join_info_list)
	{
		SpecialJoinInfo *fc_sjinfo = (SpecialJoinInfo *) lfirst(fc_lc);
		int			fc_innerrelid;
		RelOptInfo *fc_innerrel;
		Relids		fc_joinrelids;
		List	   *fc_restrictlist;

		/*
		 * 必须是一个非延迟的半连接且只连接到单个基表，
		 * 否则我们将无法对此进行任何操作。
		 * （在半连接上设置 delay_upper_joins 可能是不可能的，
		 * 但我们还是可以检查一下。）
		 */
		if (fc_sjinfo->jointype != JOIN_SEMI ||
			fc_sjinfo->delay_upper_joins)
			continue;

		if (!bms_get_singleton_member(fc_sjinfo->min_righthand, &fc_innerrelid))
			continue;

		fc_innerrel = find_base_rel(fc_root, fc_innerrelid);

		/*
		 * 在我们费心运行 generate_join_implied_equalities 之前，
		 * 快速检查以消除那些我们肯定无法证明内关系唯一性的情况。
		 */
		if (!fc_rel_supports_distinctness(fc_root, fc_innerrel))
			continue;

		/* 计算我们正在考虑的连接的 relid 集合 */
		fc_joinrelids = bms_union(fc_sjinfo->min_lefthand, fc_sjinfo->min_righthand);

		/*
		 * 由于我们仅考虑单个右侧关系，它必须有连接条件，
		 * 将其与半连接的 min_lefthand 连结。我们还可以考虑
		 * EC 派生的连接条件。
		 */
		fc_restrictlist =
			list_concat(generate_join_implied_equalities(fc_root,
														 fc_joinrelids,
														 fc_sjinfo->min_lefthand,
														 fc_innerrel),
						fc_innerrel->joininfo);

		/* 测试内关系是否对这些条件是唯一的。 */
		if (!innerrel_is_unique(fc_root,
								fc_joinrelids, fc_sjinfo->min_lefthand, fc_innerrel,
								JOIN_SEMI, fc_restrictlist, true))
			continue;

		/* 好的，从列表中移除 SpecialJoinInfo。 */
		fc_root->join_info_list = foreach_delete_current(fc_root->join_info_list, fc_lc);
	}
}


/*
 * rel_supports_distinctness
 *		这个关系是否可能在某些列上被证明是唯一的？
 *
 * 这实际上是 rel_is_distinct_for() 的预检查函数。
 * 如果 rel_is_distinct_for() 可能返回真，这个函数必须返回真，
 * 但不应该消耗太多处理周期。其思想是，调用者可以避免在
 * 调用不可能成功的情况下进行可能昂贵的处理来计算
 * rel_is_distinct_for() 的参数列表。
 */
static bool fc_rel_supports_distinctness(PlannerInfo *fc_root, RelOptInfo *fc_rel)
{
	/* 我们只知道基表 ... */
	if (fc_rel->reloptkind != RELOPT_BASEREL)
		return false;
	if (fc_rel->rtekind == RTE_RELATION)
	{
		/*
		 * 对于普通关系，我们只能通过引用唯一索引来证明唯一性。
		 * 确保至少有一个合适的唯一索引。它必须被立即强制执行，
		 * 而不是部分索引。（保持这些条件与
		 * relation_has_unique_index_for! 同步。）
		 */
		ListCell   *fc_lc;

		foreach(fc_lc, fc_rel->indexlist)
		{
			IndexOptInfo *fc_ind = (IndexOptInfo *) lfirst(fc_lc);

			if (fc_ind->unique && fc_ind->immediate && fc_ind->indpred == NIL)
				return true;
		}
	}
	else if (fc_rel->rtekind == RTE_SUBQUERY)
	{
		Query	   *fc_subquery = fc_root->simple_rte_array[fc_rel->relid]->subquery;

		/* 检查子查询是否具有支持唯一性的任何属性 */
		if (query_supports_distinctness(fc_subquery))
			return true;
	}
	/* 对于其他 rtekinds，我们没有证明规则。 */
	return false;
}


/*
 * rel_is_distinct_for
 *		这个关系是否仅根据 clause_list 返回唯一行？
 *
 * clause_list 是涉及此关系和其他一些关系的连接限制子句的列表。如果此关系发出的两行可能连接到另一关系的同一行，则返回真。
 *
 * 调用者必须已经确定每个条件都是一个可合并连接的相等式，一边是此关系的表达式，另一边是没有涉及此关系的表达式。临时的 outer_is_left 标志用于识别哪个侧引用此关系：如果 outer_is_left 为 false，则是左侧；如果为 true，则是右侧。
 *
 * 请注意，传入的 clause_list 可能会被破坏性修改！这在当前用途下是可以的，因为 clause_list 是由调用者构建的，目的仅仅是传递给这个函数。
 */
static bool fc_rel_is_distinct_for(PlannerInfo *fc_root, RelOptInfo *fc_rel, List *fc_clause_list)
{
	/*
	 * 如果我们假设所有调用者首先检查了 rel_supports_distinctness，我们可以跳过几个测试，但似乎没有必要冒这个风险。
	 */
	if (fc_rel->reloptkind != RELOPT_BASEREL)
		return false;
	if (fc_rel->rtekind == RTE_RELATION)
	{
		/*
		 * 检查索引以查看我们是否拥有匹配的唯一索引。
		 * relation_has_unique_index_for 会自动添加任何可用的限制子句，因此我们在这里不需要这样做。
		 */
		if (relation_has_unique_index_for(fc_root, fc_rel, fc_clause_list, NIL, NIL))
			return true;
	}
	else if (fc_rel->rtekind == RTE_SUBQUERY)
	{
		Index		fc_relid = fc_rel->relid;
		Query	   *fc_subquery = fc_root->simple_rte_array[fc_relid]->subquery;
		List	   *fc_colnos = NIL;
		List	   *fc_opids = NIL;
		ListCell   *fc_l;

		/*
		 * 为 query_is_distinct_for 构建参数列表：查询需要在其上保持唯一的输出列号的列表，以及输出列需要根据的相等操作符列表。
		 *
		 * (XXX 我们没有考虑附加到子查询的限制子句；是否值得这么做？)
		 */
		foreach(fc_l, fc_clause_list)
		{
			RestrictInfo *fc_rinfo = lfirst_node(RestrictInfo, fc_l);
			Oid			fc_op;
			Var		   *fc_var;

			/*
			 * 获取我们需要的相等操作符以确保唯一性。
			 * （这可能是一个跨类型操作符，因此可能与子查询考虑的操作符完全不同；这没关系，因为 query_is_distinct_for 可以解决这种情况。）调用者的合并连接测试应该只选择 OpExprs。
			 */
			fc_op = castNode(OpExpr, fc_rinfo->clause)->opno;

			/* 调用者为我们识别了内侧 */
			if (fc_rinfo->outer_is_left)
				fc_var = (Var *) get_rightop(fc_rinfo->clause);
			else
				fc_var = (Var *) get_leftop(fc_rinfo->clause);

			/*
			 * 我们可以忽略操作数上方的任何 RelabelType 节点。
			 * （不会超过一个，因为 eval_const_expressions() 已经被应用过。）
			 */
			if (fc_var && IsA(fc_var, RelabelType))
				fc_var = (Var *) ((RelabelType *) fc_var)->arg;

			/*
			 * 如果内侧不是引用子查询输出列的 Var，这个子句对我们没有帮助。
			 */
			if (!fc_var || !IsA(fc_var, Var) ||
				fc_var->varno != fc_relid || fc_var->varlevelsup != 0)
				continue;

			fc_colnos = lappend_int(fc_colnos, fc_var->varattno);
			fc_opids = lappend_oid(fc_opids, fc_op);
		}

		if (query_is_distinct_for(fc_subquery, fc_colnos, fc_opids))
			return true;
	}
	return false;
}


/*
 * query_supports_distinctness - 查询是否可能在某组输出列上被证明是唯一的？
 *
 * 这是 query_is_distinct_for() 的有效预检查功能。
 * 如果 query_is_distinct_for() 在此查询的情况下可能返回真，则必须返回真，但它不应消耗大量周期。其思想是，如果调用无法成功，则调用者可以避免进行可能昂贵的处理来计算 query_is_distinct_for() 的参数列表。
 */
bool query_supports_distinctness(Query *fc_query)
{
	/* SRFs 除非使用 DISTINCT，否则会破坏唯一性，见下文 */
	if (fc_query->hasTargetSRFs && fc_query->distinctClause == NIL)
		return false;

	/* 检查我们可以证明不同特征的情况 */
	if (fc_query->distinctClause != NIL ||
		fc_query->groupClause != NIL ||
		fc_query->groupingSets != NIL ||
		fc_query->hasAggs ||
		fc_query->havingQual ||
		fc_query->setOperations)
		return true;

	return false;
}

/*
 * query_is_distinct_for - 查询是否从不返回指定列的重复值？
 *
 * query 是一个尚未计划的子查询（在当前使用中，它总是来自子查询 RTE，规划器避免对其进行修改）。
 *
 * colnos 是一个输出列编号的整数列表（resno's）。我们感兴趣的是，仅由这些列组成的行是否一定是不同的。“不同性”的定义基于 opids 列表中相应的上级等式运算符是否会认为这些值是不同的。（注意：opids 条目可能是跨类型运算符，因此不一定是子查询自己将使用的等式运算符。我们使用 equality_ops_are_compatible() 来检查兼容性。那个函数检查 btree 或 hash opfamily 的成员资格，因此应该为我们可能在这里处理的所有运算符提供可靠的答案。）
*/
bool query_is_distinct_for(Query *fc_query, List *fc_colnos, List *fc_opids)
{
	ListCell   *fc_l;
	Oid			fc_opid;

	Assert(list_length(fc_colnos) == list_length(fc_opids));

	/*
	 * DISTINCT（包括 DISTINCT ON）保证唯一性如果 DISTINCT 子句中
	 * 所有的列都出现在 colnos 中且运算符语义匹配。即使在 DISTINCT 列中
	 * 或 tlist 其他地方存在 SRF 也是如此。
	 */
	if (fc_query->distinctClause)
	{
		foreach(fc_l, fc_query->distinctClause)
		{
			SortGroupClause *fc_sgc = (SortGroupClause *) lfirst(fc_l);
			TargetEntry *fc_tle = get_sortgroupclause_tle(fc_sgc,
													   fc_query->targetList);

			fc_opid = fc_distinct_col_search(fc_tle->resno, fc_colnos, fc_opids);
			if (!OidIsValid(fc_opid) ||
				!equality_ops_are_compatible(fc_opid, fc_sgc->eqop))
				break;			/* 如果没有匹配则提前退出 */
		}
		if (fc_l == NULL)			/* 所有的匹配都存在吗？ */
			return true;
	}

	/*
	 * 否则，查询的目标列表中的返回集函数可能会导致返回重复行，
	 * 尽管在 tlist 评估之前可能会发生任何分组。（如果所有 tlist SRF
	 * 都在 GROUP BY 列中，那么这就安全，因为它们将在分组之前扩展。
	 * 但目前似乎没有必要检查这一点。）
	 */
	if (fc_query->hasTargetSRFs)
		return false;

	/*
	 * 类似地，如果没有 GROUPING SETS 的 GROUP BY 保证唯一性，
	 * 如果所有分组列都出现在 colnos 中且运算符语义匹配。
	 */
	if (fc_query->groupClause && !fc_query->groupingSets)
	{
		foreach(fc_l, fc_query->groupClause)
		{
			SortGroupClause *fc_sgc = (SortGroupClause *) lfirst(fc_l);
			TargetEntry *fc_tle = get_sortgroupclause_tle(fc_sgc,
													   fc_query->targetList);

			fc_opid = fc_distinct_col_search(fc_tle->resno, fc_colnos, fc_opids);
			if (!OidIsValid(fc_opid) ||
				!equality_ops_are_compatible(fc_opid, fc_sgc->eqop))
				break;			/* 如果没有匹配则提前退出 */
		}
		if (fc_l == NULL)			/* 所有的匹配都存在吗？ */
			return true;
	}
	else if (fc_query->groupingSets)
	{
		/*
		 * 如果我们有带表达式的分组集，那么我们可能没有唯一性，
		 * 分析将会很困难。放弃。
		 */
		if (fc_query->groupClause)
			return false;

		/*
		 * 如果我们没有 groupClause（因此没有分组表达式），那么我们
		 * 可能有一个或多个空分组集。如果只有一个，那么我们只返回一行，
		 * 且肯定是唯一的。但否则，我们知道我们肯定不是唯一的。
		 */
		if (list_length(fc_query->groupingSets) == 1 &&
			((GroupingSet *) linitial(fc_query->groupingSets))->kind == GROUPING_SET_EMPTY)
			return true;
		else
			return false;
	}
	else
	{
		/*
		 * 如果我们没有 GROUP BY，但有聚合或 HAVING，那么结果最多
		 * 只有一行，所以对于任何运算符都是肯定唯一的。
		 */
		if (fc_query->hasAggs || fc_query->havingQual)
			return true;
	}

	/*
	 * UNION、INTERSECT、EXCEPT 保证整个输出行的唯一性，除了 ALL。
	 */
	if (fc_query->setOperations)
	{
		SetOperationStmt *fc_topop = castNode(SetOperationStmt, fc_query->setOperations);

		Assert(fc_topop->op != SETOP_NONE);

		if (!fc_topop->all)
		{
			ListCell   *fc_lg;

			/* 如果所有非冗余输出列都在 colnos 中，那就没问题 */
			fc_lg = list_head(fc_topop->groupClauses);
			foreach(fc_l, fc_query->targetList)
			{
				TargetEntry *fc_tle = (TargetEntry *) lfirst(fc_l);
				SortGroupClause *fc_sgc;

				if (fc_tle->resjunk)
					continue;	/* 忽略 resjunk 列 */

				/* 非冗余列应该有分组子句 */
				Assert(fc_lg != NULL);
				fc_sgc = (SortGroupClause *) lfirst(fc_lg);
				fc_lg = lnext(fc_topop->groupClauses, fc_lg);

				fc_opid = fc_distinct_col_search(fc_tle->resno, fc_colnos, fc_opids);
				if (!OidIsValid(fc_opid) ||
					!equality_ops_are_compatible(fc_opid, fc_sgc->eqop))
					break;		/* 如果没有匹配则提前退出 */
			}
			if (fc_l == NULL)		/* 所有的匹配都存在吗？ */
				return true;
		}
	}

	/*
	 * XXX 还有其他我们可以轻松看出结果必须是不同的情况吗？
	 *
	 * 如果您向此函数添加更多智能，请务必更新
	 * query_supports_distinctness() 以匹配。
	 */

	return false;
}

/*
 * distinct_col_search - query_is_distinct_for 的子例程
 *
 * 如果 colno 在 colnos 中，则返回对应的 opids 元素，
 * 否则返回 InvalidOid。（通常 colnos 不会包含重复项，
 * 但如果有，我们任意选择第一个匹配项。）
 */
static Oid fc_distinct_col_search(int fc_colno, List *fc_colnos, List *fc_opids)
{
	ListCell   *fc_lc1,
			   *fc_lc2;

	forboth(fc_lc1, fc_colnos, fc_lc2, fc_opids)
	{
		if (fc_colno == lfirst_int(fc_lc1))
			return lfirst_oid(fc_lc2);
	}
	return InvalidOid;
}


/*
 * innerrel_is_unique
 *	  检查 innerrel 是否可以证明最多只包含一个与每个
 *	  outerrel 中的元组匹配的元组，基于 'restrictlist' 中的连接子句。
 *
 * 我们需要一个实际的 RelOptInfo 对于 innerrel，但识别 outerrel 的
 * Relids 是足够的。这种不对称支持在构建 joinrels 之前使用此函数。
 * （调用者预计还将提供 joinrelids，以免重新计算。）
 *
 * 证明必须仅基于执行时将成为“joinquals”的子句，而不是“otherquals”。
 * 对于内部连接没有区别；但如果连接是外部的，我们必须忽略下推的 quals，
 * 因为这些将变为“otherquals”。请注意，这意味着答案可能会根据
 * IS_OUTER_JOIN(jointype) 的结果而有所不同；由于我们在不考虑该条件的
 * 情况下缓存答案，调用者必须注意不要以 IS_OUTER_JOIN() 会
 * 不同分类的 jointypes 调用此函数。
 *
 * 实际证明由 is_innerrel_unique_for() 完成；此函数是一个前端，
 * 主要关注缓存答案。特别是，force_cache 参数允许覆盖有关
 * 是否缓存负答案的内部启发式；如果进行的查询不是正常自下而上的
 * 连接搜索序列的一部分，则应该为“true”。
 */
bool innerrel_is_unique(PlannerInfo *fc_root,
				   Relids fc_joinrelids,
				   Relids fc_outerrelids,
				   RelOptInfo *fc_innerrel,
				   JoinType fc_jointype,
				   List *fc_restrictlist,
				   bool fc_force_cache)
{
	MemoryContext fc_old_context;
	ListCell   *fc_lc;

	/* 显然无法证明没有连接子句时的唯一性 */
	if (fc_restrictlist == NIL)
		return false;

	/*
	 * 快速检查一下，以排除我们肯定无法证明 innerrel 唯一性的情况。
	 */
	if (!fc_rel_supports_distinctness(fc_root, fc_innerrel))
		return false;

	
/*
	 * 查询缓存，看看我们是否设法证明 innerrel 在任何 subset 的 outerrel 中是唯一的。
	 * 我们不需要完全匹配，因为额外的 outerrels 不会使 innerrel 的唯一性降低（或者更正式地说，对一个 superset outerrel 的连接的 restrictlist 必须是我们之前成功使用的条件的 superset）。
	 */
	foreach(fc_lc, fc_innerrel->unique_for_rels)
	{
		Relids		fc_unique_for_rels = (Relids) lfirst(fc_lc);

		if (bms_is_subset(fc_unique_for_rels, fc_outerrelids))
			return true;		/* 成功！ */
	}

	/*
	 * 相反，我们可能已经确定这个 outerrel，或其某个 superset，不能证明这个 innerrel 是唯一的。
	 */
	foreach(fc_lc, fc_innerrel->non_unique_for_rels)
	{
		Relids		fc_unique_for_rels = (Relids) lfirst(fc_lc);

		if (bms_is_subset(fc_outerrelids, fc_unique_for_rels))
			return false;
	}

	/* 没有缓存信息，所以尝试进行证明。 */
	if (fc_is_innerrel_unique_for(fc_root, fc_joinrelids, fc_outerrelids, fc_innerrel,
							   fc_jointype, fc_restrictlist))
	{
		/*
		 * 缓存积极结果以供未来查询，确保即使我们在 GEQO 下工作，也要将其保存在 planner_cxt 中。
		 *
		 * 注意：可以考虑尝试隔离证明 innerrel 唯一的 outerrels 的最小子集。 
		 * 但是这并不值得麻烦，因为规划器是增量构建 joinrels 的，因此我们会先看到最小足够的 outerrels，而不是它们的任何 supersets。
		 */
		fc_old_context = MemoryContextSwitchTo(fc_root->planner_cxt);
		fc_innerrel->unique_for_rels = lappend(fc_innerrel->unique_for_rels,
											bms_copy(fc_outerrelids));
		MemoryContextSwitchTo(fc_old_context);

		return true;			/* 成功！ */
	}
	else
	{
		/*
		 * 外部连接的条件没有证明 innerrel 是唯一的，因此我们可以在未来的检查中安全地拒绝这个 outerrel 或其任何子集。
		 *
		 * 然而，在正常规划模式下，缓存这个知识完全没有意义；它不会再被查询，因为我们是从小到大构建 joinrels 的。
		 * 在 GEQO 模式下，它是有用的，因为这个知识可以跨越连续的规划尝试传递；并且在使用 join-search 插件时可能也会有用。
		 * 因此，当 join_search_private 非 NULL 时缓存这个知识。 （好吧，这算是一种hack，但似乎合理。）
		 *
		 * 此外，允许调用者覆盖该启发式并强制缓存；这对于在正常连接搜索开始之前调用这里的 reduce_unique_semijoins 是有用的。
		 */
		if (fc_force_cache || fc_root->join_search_private)
		{
			fc_old_context = MemoryContextSwitchTo(fc_root->planner_cxt);
			fc_innerrel->non_unique_for_rels =
				lappend(fc_innerrel->non_unique_for_rels,
						bms_copy(fc_outerrelids));
			MemoryContextSwitchTo(fc_old_context);
		}

		return false;
	}
}

/*
 * is_innerrel_unique_for
 *	  检查 innerrel 是否可以证明最多包含一个与 outerrel 中任何 tuple 匹配的 tuple，
 *	  基于 'restrictlist' 中的连接条件。
 */
static bool fc_is_innerrel_unique_for(PlannerInfo *fc_root,
					   Relids fc_joinrelids,
					   Relids fc_outerrelids,
					   RelOptInfo *fc_innerrel,
					   JoinType fc_jointype,
					   List *fc_restrictlist)
{
	List	   *fc_clause_list = NIL;
	ListCell   *fc_lc;

	/*
	 * 搜索约束 inner rel 与 outer rel 的合并连接条件。 
	 * 如果一个操作符是合并连接的，那么它在某个 btree opclass 中表现得像等值操作，因此这是我们想要的。
	 * 合并连接性测试还消除了包含易变函数的条件，我们无法依赖这些函数。
	 */
	foreach(fc_lc, fc_restrictlist)
	{
		RestrictInfo *fc_restrictinfo = (RestrictInfo *) lfirst(fc_lc);

		/*
		 * 如上所述，如果它是一个下推的条件并且我们处于外连接中，我们不能使用它。
		 */
		if (IS_OUTER_JOIN(fc_jointype) &&
			RINFO_IS_PUSHED_DOWN(fc_restrictinfo, fc_joinrelids))
			continue;

		/* 如果不是可合并连接子句，则忽略 */
		if (!fc_restrictinfo->can_join ||
			fc_restrictinfo->mergeopfamilies == NIL)
			continue;			/* 不是可合并连接的 */

		/*
 * 检查子句是否具有“外部 op 内部”或“内部 op 外部”的形式，
 * 如果是，则标记哪个侧是内部。
 */
		if (!fc_clause_sides_match_join(fc_restrictinfo, fc_outerrelids,
									 fc_innerrel->relids))
			continue;			/* 对这些输入关系不适用 */

		/* 好的，添加到列表 */
		fc_clause_list = lappend(fc_clause_list, fc_restrictinfo);
	}

	/* 让 rel_is_distinct_for() 做繁重的工作 */
	return fc_rel_is_distinct_for(fc_root, fc_innerrel, fc_clause_list);
}
